package LeetCode.interview;

import util.LogUtils;
import LeetCode.junit.Solution;

/*
 * 
 原题

 Write a function to find the longest common prefix string amongst an array of strings. 

 题目大意

 写一个函数找出一个字串所数组中的最长的公共前缀。 

 解题思路

 第一步先找出长度最小的字符串，然后将这个字符串与其它的字符串相比找出最短的最公共前缀。 
 * @Date 2017-09-12 16：10
 */
public class _014_Longest_Common_Prefix {
	
	/**
	 * 暴力查找。。。
	 * @param strs
	 * @return
	 */
	public String longestCommonPrefix(String[] strs) {
		if (strs == null)
			return null;
		if (strs.length == 0)
			return "";

		// 找出最短的字符串的长度
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < strs.length; i++) {
			if (strs[i] == null)
				return null;
			if (min > strs[i].length()) {
				min = strs[i].length();
			}
		}

		// 找出公用的最长前缀
		int i = 0;
		boolean flag = false; // 判断是否找到
		for (i = 0; i < min; i ++) {
			flag = true;
			// 遍历每个字符串
			for (int j = 1; j < strs.length; j ++) {
				if (strs[0].charAt(i) != strs[j].charAt(i)) {
					flag = false;
					break;
				}
			}
            if (!flag) {							
                break;
            }
		}
		return strs[0].substring(0, i);
	}

	public static void main(String[] args) {
		LogUtils.println("结果", new _014_Longest_Common_Prefix()
				.longestCommonPrefix(new String[] { "zouch", "zou"}));
	}
}
